package acwing.闫氏DP分析法;
import java.util.*;
public class DP01背包{
    public static void main(String[] args){
        int n,v;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        v = sc.nextInt();
        int[] v1 = new int[n+1];
        int[] w = new int[n+1];
        int[][] f = new int[n+1][v+1];
        for(int i=1;i<=n;i++){
        
            v1[i]= sc.nextInt();   
            w[i] = sc.nextInt();
     }
     for(int i=1;i<=n;i++){
         for(int j=0;j<=v;j++){
             f[i][j]= f[i-1][j];
             if(j>=v1[i]){
                 f[i][j]=Math.max(f[i][j],f[i-1][j-v1[i]]+w[i]);
             }
         }
     }
     sc.close();
     System.out.println(f[n][v]);
    }
}